package flashBack;

/**
 * @author zxc
 * @date 2023/01/17 14:50
 **/

import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：分割回文子字符串
 * 题目详述 ：
 * 给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
 * 回文串 是正着读和反着读都一样的字符串。
 */
public class Partition {
    /**
     *  思路 ：回溯法实现
     *  ===》 对于字符串str中当前遍历的字符，如果包含此字符在内后面还有n个字符的话，那么此时就面临n个选择;
     *        即，在这n个选择中选择出能够构成回文字符串的子字符串;
     */
    public List<List<String>> partition(String s) {
        List<List<String>> result = new LinkedList<>();
        flushBack(s , 0 ,new LinkedList<String>() , result);
//        String[][] array = new String[result.size()][];
//        int i = -1;
//        for (List<String> list : result) {
//            if(list != null){
//                i++;
//                int j = 0;
//                array[i] = new String[list.size()];
//                for (String str : list) {
//                    if(i < result.size() && j < result.size()){
//                        array[i][j++] = str;
//                    }
//                }
//            }
//        }
//        return array;
        return result;
    }
    // 回溯法 ：获取分割字符串str===》子字符串 && 字符串为回文字符串的所有结果;
    private void flushBack(String str, int index , LinkedList<String> substrings, List<List<String>> result) {
        // 对于字符串str进行分割后，符合条件的子字符串集，将其加入到result集合中;
        if(index == str.length()){
            // 回溯法的另一个核心 ：由于substrings需要通过其来实现回溯法，所以只能够向结果数组中添加当前符合条件的substrings拷贝;
            result.add(new LinkedList<>(substrings));
            return;
        }
        // 对于字符串str中当前遍历的字符，如果包含此字符在内后面还有n个字符的话，那么此时就面临n个选择;
        for(int end = index ; end < str.length() ; end++){
            // 若是该子字符串childStr为回文字符串的话，才能将其加入到substrings中 && 可以接着分割后面的字符串
            if(isPalindrome(str , index , end)){
                // 即，将str字符串中(index , end + 1)这段子字符串加入到substrings集合中;
                // str.substring（start ， end）方法，所截取的字符串为str中从start到end - 1的子字符串;
                substrings.add(str.substring(index , end + 1));
                // 字符起始位置为end + 1;
                flushBack(str , end + 1 , substrings , result);
                // 回溯法核心 ：回退之前的修改操作
                substrings.removeLast();
            }
        }
    }
    // 判断当前子字符串childStr，是否为回文字符串
    private boolean isPalindrome(String str, int index, int end) {
        while(index < end){
            // 若是所传入的字符串str不满足回文字符串的话，直接返回false即可;
            if(str.charAt(index++) != str.charAt(end--)){
                return false;
            }
        }
        return true;
    }
}
